인접 정점

무방향 그래프에서 인접 정점의 관계는 항상 상호적이다. 즉, 정점 A가 정점 B의 인접 정점이라면, 정점 B도 정점 A의 인접 정점이다. 이는 두 정점을 잇는 간선에 방향성이 없기 때문으로, 간선은 단순히 두 정점 사이의 연결 관계만을 나타낸다. 따라서 무방향 그래프에서의 인접성은 대칭 관계를 가진다.

이러한 특성은 인접 행렬 표현에서도 명확히 드러난다. 무방향 그래프의 인접 행렬은 주대각선을 기준으로 대칭인 구조를 가지며, 정점 i와 j가 인접하면 행렬의 (i, j) 요소와 (j, i) 요소 모두 1의 값을 가진다. 마찬가지로 인접 리스트에서도 정점 A의 리스트에 B가 포함되어 있다면, 정점 B의 리스트에도 A가 포함된다.

무방향 그래프에서의 인접 관계는 네트워크 이론에서 친구 관계나 협력 관계와 같은 상호 작용을 모델링하는 데 적합하다. 예를 들어, 소셜 네트워크에서 두 사람이 서로 친구라면, 이는 무방향 간선으로 표현되며 각자는 서로의 인접 정점이 된다. 이러한 대칭적 연결의 개념은 그래프 탐색이나 커뮤니티 탐지와 같은 분석의 기초가 된다.

방향 그래프에서는 간선에 방향이 존재합니다. 따라서 정점 A에서 정점 B로 향하는 간선이 있을 때, 정점 B는 정점 A의 인접 정점이지만, 그 역은 성립하지 않습니다. 이 경우 정점 A는 정점 B의 인접 정점이 아닙니다. 이러한 관계를 비대칭적이라고 표현합니다.

방향 그래프에서의 인접성은 출발 정점과 도착 정점을 명확히 구분해야 합니다. 예를 들어, 정점 u에서 정점 v로 향하는 간선 (u, v)가 있다면, v는 u의 외접 정점 또는 후행 정점이라고 부르며, u는 v의 내접 정점 또는 선행 정점이라고 부릅니다. 이는 네트워크 이론이나 유한 상태 기계 모델링에서 상태 전이를 표현할 때 중요한 개념이 됩니다.

방향 그래프의 인접 관계는 인접 행렬로 표현할 때도 비대칭 행렬이 됩니다. 즉, 행렬의 (i, j) 성분과 (j, i) 성분이 일반적으로 일치하지 않습니다. 또한 인접 리스트를 구성할 때는 각 정점마다 그 정점에서 직접 도달할 수 있는 정점들의 목록만을 관리하는 것이 일반적입니다. 이러한 특성은 위상 정렬이나 강한 연결 요소 탐색과 같은 알고리즘의 동작 방식에 직접적인 영향을 미칩니다.

가중 그래프에서 인접 정점의 개념은 간선에 부여된 가중치와 밀접한 연관을 가진다. 무방향 그래프나 방향 그래프와 마찬가지로 두 정점이 간선으로 직접 연결되어 있으면 서로 인접 정점이지만, 여기에 각 연결의 강도, 비용, 거리 등을 나타내는 숫자 값인 가중치가 추가 정보로 부여된다. 이는 도로 네트워크에서 거리나 통행 시간, 통신 네트워크에서 대역폭이나 지연 시간, 소셜 네트워크에서 관계의 친밀도 등을 모델링할 때 유용하다.

가중 그래프에서의 인접성은 단순한 연결 여부를 넘어, 그 연결의 '양'을 고려한 분석의 기초가 된다. 예를 들어, 최단 경로 알고리즘인 다익스트라 알고리즘이나 플로이드-워셜 알고리즘은 출발 정점에서 목표 정점까지 도달하는 데 거치는 인접 정점들을 탐색하며, 각 간선의 가중치를 합산하여 최소 비용 경로를 찾는다. 이때 알고리즘은 현재 정점의 모든 인접 정점을 검토하고, 가중치를 기준으로 다음에 방문할 정점의 우선순위를 결정한다.

데이터 구조 측면에서 가중 그래프를 표현할 때, 인접 행렬은 각 셀에 간선의 존재 여부(0 또는 1) 대신 가중치 값을 저장하며, 간선이 없음을 나타내기 위해 무한대(∞)나 0 같은 특정 값을 사용한다. 인접 리스트 역시 각 정점에 연결된 인접 정점의 목록을 저장할 때, 함께 해당 간선의 가중치를 쌍으로 저장하여 관리한다. 이러한 표현 방식은 그래프 이론을 적용한 네트워크 분석이나 경로 최적화 문제를 해결하는 데 필수적이다.

그래프 이론에서 어떤 정점의 차수는 그 정점에 연결된 간선의 수를 의미한다. 무방향 그래프에서는 해당 정점에 인접한 정점의 개수와 일치한다. 예를 들어, 어떤 정점에서 세 개의 간선이 뻗어 나와 있다면 그 정점의 차수는 3이다.

방향 그래프에서는 차수가 진입 차수와 진출 차수로 구분된다. 진입 차수는 해당 정점을 향해 들어오는 간선의 수이며, 진출 차수는 해당 정점에서 나가는 간선의 수이다. 이는 네트워크 분석에서 중요한 지표가 되며, 예를 들어 소셜 네트워크에서 진입 차수는 인기도를, 진출 차수는 활동성을 나타낼 수 있다.

차수는 그래프의 구조적 특성을 파악하는 데 핵심적인 역할을 한다. 모든 정점의 차수를 합하면 간선 수의 두 배가 되며, 이는 차수의 합에 관한 정리로 알려져 있다. 또한, 모든 정점의 차수가 같은 그래프를 정규 그래프라고 부른다. 차수 분포는 랜덤 그래프나 스케일 프리 네트워크와 같은 복잡 네트워크의 특성을 연구하는 데 필수적이다.

알고리즘 설계에서도 차수는 중요한 요소이다. 너비 우선 탐색이나 깊이 우선 탐색과 같은 그래프 탐색 알고리즘은 정점의 인접 정점, 즉 차수에 해당하는 연결들을 순회한다. 또한, 오일러 경로가 존재하기 위한 필요 조건은 홀수 차수를 가진 정점이 0개 또는 2개여야 한다는 것이다.

인접 행렬은 그래프 이론에서 그래프의 구조를 행렬 형태로 표현하는 방법이다. 그래프의 정점 개수가 n개일 때, n x n 크기의 정방행렬을 사용하며, 행렬의 각 요소는 두 정점 사이의 연결 관계를 나타낸다. 일반적으로 두 정점 i와 j 사이에 간선이 존재하면 행렬의 (i, j) 위치 값을 1로, 존재하지 않으면 0으로 표시한다. 이 표현 방식은 특정 두 정점이 서로 인접 정점인지 여부를 상수 시간(O(1))에 확인할 수 있다는 장점이 있다.

그러나 인접 행렬은 메모리 사용 측면에서 비효율적일 수 있다. 정점이 n개인 그래프는 항상 n^2 크기의 행렬을 필요로 하기 때문에, 간선의 수가 적은 희소 그래프의 경우 많은 공간이 낭비된다. 또한 그래프에 새로운 정점을 추가하거나 삭제하는 작업이 상대적으로 복잡하다는 단점도 있다. 이러한 특성으로 인해 인접 행렬은 밀집 그래프나 정점의 수가 비교적 적은 그래프를 표현할 때 주로 활용된다.

인접 행렬은 방향성과 가중치를 포함한 그래프 표현에도 확장 적용된다. 방향 그래프에서는 간선의 방향성을 반영하여, 정점 i에서 j로 가는 간선이 있을 때만 (i, j) 위치를 1로 채운다. 가중 그래프의 경우, 행렬 요소에 간선의 존재 여부 대신 가중치 값을 직접 저장하여 표현한다. 이는 최단 경로 알고리즘이나 네트워크 흐름 분석 등 다양한 알고리즘의 기초 자료 구조로 사용된다.

인접 리스트는 그래프를 표현하는 대표적인 자료 구조 중 하나이다. 이 방식은 각 정점마다 그 정점에 인접한 모든 정점의 목록을 저장한다. 무방향 그래프의 경우, 두 정점이 서로 인접하면 각 정점의 리스트에 상대방이 포함된다. 방향 그래프에서는 각 정점에서 나가는 간선에 대한 인접 정점만을 리스트에 저장하는 것이 일반적이다.

인접 리스트의 주요 장점은 메모리 사용 효율성이다. 실제 존재하는 간선의 수만큼만 정보를 저장하므로, 간선이 상대적으로 적은 희소 그래프를 표현할 때 매우 효율적이다. 이는 모든 가능한 정점 쌍의 연결 관계를 행렬 형태로 저장하는 인접 행렬과 대비되는 특징이다. 또한, 특정 정점에 연결된 모든 인접 정점을 빠르게 순회할 수 있어 그래프 탐색 알고리즘 구현에 적합하다.

반면, 두 정점 사이에 특정 간선이 존재하는지 확인하는 연산은 리스트를 순차 탐색해야 하므로 인접 행렬에 비해 느릴 수 있다. 이러한 특성 때문에 밀집 그래프나 간선 존재 여부를 빈번히 확인해야 하는 알고리즘에서는 인접 행렬이 더 유리할 수 있다. 인접 리스트는 깊이 우선 탐색, 너비 우선 탐색, 다익스트라 알고리즘 등 많은 그래프 알고리즘의 기반이 되는 핵심 구조이다.

너비 우선 탐색(BFS)은 그래프나 트리의 모든 정점을 체계적으로 방문하는 그래프 탐색 알고리즘이다. 이 알고리즘은 시작 정점에서 가장 가까운, 즉 시작 정점으로부터 가장 적은 수의 간선을 거쳐 도달할 수 있는 정점들을 우선적으로 방문하는 전략을 사용한다. 이 과정에서 현재 정점의 인접 정점 목록을 확인하고, 아직 방문하지 않은 인접 정점들을 방문 예정 큐에 추가하는 방식으로 작동한다.

BFS의 핵심 동작은 큐 자료구조를 활용하여 방문 순서를 관리하는 데 있다. 알고리즘은 시작 정점을 방문하고 큐에 넣는다. 이후 큐의 맨 앞에서 정점을 꺼내어, 그 정점의 모든 인접 정점을 검사한다. 검사 중 아직 방문하지 않은 인접 정점이 발견되면, 해당 정점을 방문 처리한 후 큐의 맨 뒤에 삽입한다. 이 과정을 큐가 빌 때까지 반복함으로써 그래프의 모든 연결된 정점을 시작점으로부터 거리 순으로 탐색하게 된다.

이 알고리즘은 두 정점 사이의 최단 경로를 찾거나, 네트워크에서 연결된 구성 요소를 발견하는 등 다양한 문제 해결에 응용된다. BFS의 효율성은 그래프를 표현하는 데 사용되는 자료구조, 즉 인접 행렬이나 인접 리스트에 크게 의존하며, 각 정점과 간선을 정확히 한 번씩만 처리한다는 특징이 있다.

깊이 우선 탐색은 그래프나 트리의 모든 정점을 탐색하는 알고리즘으로, 인접 정점의 개념을 기반으로 작동한다. 이 알고리즘은 현재 정점에서 방문하지 않은 인접 정점 중 하나를 선택해 깊게 들어가 탐색을 계속하는 방식을 취한다. 더 이상 방문할 수 있는 인접 정점이 없으면 이전 정점으로 돌아와 다른 인접 정점을 탐색하는 백트래킹 방식을 사용한다. 스택 자료구조를 사용하거나 재귀 호출을 통해 구현할 수 있다.

깊이 우선 탐색은 인접 정점을 처리하는 순서에 따라 다양한 응용이 가능하다. 예를 들어, 위상 정렬, 강한 연결 요소 탐색, 사이클 검출, 미로 탐색 문제 등을 해결하는 데 활용된다. 또한, 그래프의 연결 요소를 찾거나 특정 경로를 탐색할 때도 사용된다. 알고리즘의 핵심은 각 정점을 방문했는지 여부를 표시하고, 방문하지 않은 인접 정점을 재귀적으로 탐색하는 것이다.

이 알고리즘은 인접 행렬이나 인접 리스트와 같은 그래프 표현 방식과 결합되어 효율적으로 구현된다. 인접 리스트를 사용할 경우, 각 정점의 인접 정점 목록을 순회하면 되므로 시간 복잡도는 O(V+E)가 된다. 여기서 V는 정점의 수, E는 간선의 수를 의미한다. 깊이 우선 탐색은 너비 우선 탐색과 함께 그래프 탐색의 두 기초 중 하나를 이룬다.

최단 경로 알고리즘은 그래프 상에서 두 정점 사이의 가능한 경로 중 가장 짧은 길이, 즉 가장 적은 간선 수나 가장 낮은 가중치 합을 갖는 경로를 찾는 알고리즘이다. 이러한 알고리즘들은 경로 탐색 과정에서 현재 정점의 인접 정점들을 지속적으로 확인하고 평가하는 방식으로 동작한다. 인접 정점에 대한 정보는 인접 행렬이나 인접 리스트와 같은 자료구조를 통해 효율적으로 관리된다.

대표적인 최단 경로 알고리즘으로는 다익스트라 알고리즘과 벨만-포드 알고리즘, 플로이드-워셜 알고리즘 등이 있다. 다익스트라 알고리즘은 하나의 시작 정점에서 다른 모든 정점까지의 최단 경로를 찾으며, 각 단계에서 아직 방문하지 않은 인접 정점 중 가장 가까운 정점을 선택하여 탐색을 확장한다. 벨만-포드 알고리즘은 음의 가중치를 가진 간선이 있는 그래프에서도 사용 가능하다. 플로이드-워셜 알고리즘은 모든 정점 쌍 사이의 최단 경로를 한 번에 계산한다.

이러한 알고리즘들은 네트워크 라우팅, 내비게이션 시스템, 교통망 분석, 물류 경로 최적화 등 다양한 실생활 문제 해결에 널리 적용된다. 예를 들어, GPS 내비게이션은 도로망을 가중 그래프로 모델링하고 최단 경로 알고리즘을 사용하여 최적의 이동 경로를 제공한다. 알고리즘의 성능은 그래프의 크기와 밀도, 그리고 사용된 자료구조에 크게 의존한다.